1. Field of the Invention
The present invention relates to a method and apparatus for correcting for lost data, and more particularly, to a method of correcting for the loss of data encoded using a Reed-Solomon code etc., and a lost data correction circuit thereof.
2. Description of the Related Art
Error correction is an important basic technique for improvement of the reliability of data in various types of digital systems. Various error correction codes have been proposed. Among them, a BCH code is an extremely important code in practice and is used mainly in the field of satellite communications, magnetic recording, opto-magnetic recording, etc.
It has been known that, even among the BCH codes, if a non-two dimensional BCH code such as a Reed-Solomon code is used, correction of a larger number of errors is possible if the positions of the errors are already known when the decoding is carried out. This is referred to as "lost data correction".
When a decoding system (method) that performs the usual error correction using these codes is constructed in the form of a LSI etc., the procedure used for finding an error position polynomial from a syndrome polynomial during the decoding becomes important. As a method for addressing this problem, a the process of Euclidean mutual division is effective. Specific methods for this are disclosed in, for example, (1) "A VLSI Design of a Pipeline Reed-Solomon Decoder" by Howard M. Shao et. al., IEEE Trans. on Computers Vol. C-34, May 1985, and (2) Japanese Unexamined Patent Publication No. 3-195216 by the present inventor, Japanese Unexamined Patent Publication No. 3-195217 by the present inventor, and Japanese Patent Application No. 3-254183 by the present inventor.
However, when lost data correction is carried out, the number of computations is not changed in comparison with the case of the usual correction. Rather, the computation process becomes complex and the number of numerical values to be stored during the computation becomes larger, and therefore the implementation of the method becomes difficult.
The implementation of a lost data correction circuit has been discussed in the past (for example, "Small Circuit Constitution Method by Systolic Array and Application of the Same to Reed-Solomon Coder-Decoder" by Iwamura, Imai, and Doi in Shingakushi A Vol. J72-A, No. 3, pp. 577-584, Mar. 1989). Development of LSI's for optical disks incorporating lost data correction techniques has been underway as well (for example, "Error Correction LSI for Optical Disks" by Yoshida, Yamagishi, Inoue, Ishida, and Tanaka in Shingakushi, A Vol. J73-A, No. 2, pp. 261-268, Feb. 1990), but problems remain in terms of the processing speed, circuit size, etc.
In consideration of these circumstances, the present invention provides a method of computation that simplifies the process of calculating these polynomials, which is a problem when constructing a decoder of lost data correction, and makes the storage of the polynomial coefficients during intermediate steps of the computation unnecessary. Also, it has as its object to provide a system for realizing this method of computation and the structure of the computation unit thereof.
In using an error correction decoder, it is frequently necessary to use a single decoder to correct for errors where the data has been encoded using a plurality of codes having different numbers of parity symbols and code lengths. In a system using the usual error correction code, however, for the convenience in the configuration of the encoder, code symbols are input in an inverted order. Accordingly, where lost data correction is carried out, it is necessary to have a method of finding the lost data positions counted in a forward order from additional information such as lost data flags given to the symbols when input in an inverse order.